package leetcode;



import java.util.*;

/**
 * 打开转盘锁
 */
public class LeetCode752 {

    public int openLock(String[] deadends, String target) {
        String cur = "0000";
        Set<String> dead = new HashSet<>();
        for (String deadend : deadends) dead.add(deadend);

        Set<String> visited = new HashSet<>();
        visited.add(cur);
        Queue<String> queue = new LinkedList<>();
        queue.offer(cur);
        queue.offer(null);
        int step = 0;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            if (cur == null) {
                step++;
                if (queue.peek() != null) queue.offer(null);
            } else if (cur.equals(target)) {
                return step;
            } else if (!dead.contains(cur)){
                for (int i = 0; i < 4; ++i) {
                    for (int d = -1; d <= 1; d += 2) {
                        int y = ((cur.charAt(i) - '0') + d + 10) % 10;
                        String nei = cur.substring(0, i) + ("" + y) + cur.substring(i+1);
                        if (!visited.contains(nei)) {
                            visited.add(nei);
                            queue.offer(nei);
                        }
                    }
                }
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        LeetCode752 leetCode752 = new LeetCode752();
        String[] deadends = new String[]{"0201", "0101", "0102", "1212", "2002"};
        System.out.println(leetCode752.openLock(deadends, "0202"));
    }
}